package com.gxc.dynamic;

import java.util.Arrays;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * 小明和朋友们一起玩跳格子游戏，每个格子上有特定的分数 score = [1, -1, -6, 7, -17, 7]，
 *
 * 从起点score[0]开始，每次最大的步长为k，请你返回小明跳到终点 score[n-1] 时，能得到的最大得分。
 *
 * 输入描述
 * 第一行输入总的格子数量 n
 *
 * 第二行输入每个格子的分数 score[i]
 *
 * 第三行输入最大跳的步长 k
 *
 * 备注
 * 格子的总长度 n 和步长 k 的区间在 [1, 100000]
 *
 * 每个格子的分数 score[i] 在 [-10000, 10000] 区间中
 *
 * 输出描述
 * 输出最大得分
 */
public class JumpTheGrid {

    public static void main(String[] args) {
        System.out.println(Integer.parseInt("00" + "0A", 16));
        System.out.println(Integer.parseInt("00" + "10"));

        Scanner sc = new Scanner(System.in);
        int n = Integer.parseInt(sc.nextLine());
        int[] scores = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();
        int k = Integer.parseInt(sc.nextLine());
        sc.close();

        // 特殊情况处理：如果格子数量为1，直接输出该格子的分数
        if (n == 1) {
            System.out.println(scores[0]);
            return;
        }

        // 动态规划数组，dp[i]存储到达第i个格子时能得到的最大分数
        int[] dp = new int[n];
        dp[0] = scores[0]; // 初始化，起点的最大分数就是起点的分数

        // 使用双端队列来维护窗口内的最大dp值的索引
        Deque<Integer> deque = new LinkedList<>();
        deque.add(0);

        for (int i = 1; i < n; i++) {
            // 如果队列不为空且队列头部的索引已经超出了跳跃范围，从队列中移除头部
            if (!deque.isEmpty() && deque.peekFirst() < i - k) {
                deque.pollFirst();
            }

            // 计算当前格子的最大分数：当前格子的分数加上可以跳到该格子的最大分数
            dp[i] = scores[i] + (deque.isEmpty() ? 0 : dp[deque.peekFirst()]);

            // 维护队列，保持队列为递减，新的最大值需要添加到队尾
            while (!deque.isEmpty() && dp[deque.peekLast()] <= dp[i]) {
                deque.pollLast();
            }

            // 将当前索引加到队列尾部
            deque.addLast(i);
        }

        // 输出到达最后一个格子时能得到的最大分数
        System.out.println(dp[n - 1]);
    }
}
